Users of search engines (e.g., web search engines) are often forced to sift through a long ordered list of search results in the form of documents, snippets, or text fragments, a time-consuming and inconvenient prospect in order to identify relevant topics inside the results. Existing search engines such as Google™, Yahoo™, and MSN™ often return a review the list and examine the titles and (short) snippets sequentially in order to identify their desired results. This is an even more time consuming task when multiple sub-topics of the given query are mixed together. For example, when a user submits a query “jaguar” into Google and wants to get search results related to “big cats”, he or she might need to go to the 10th, 11th, 32nd, and/or 71st results.
A possible solution to this problem is to (online) cluster search results into different groups, and to enable users to identify their required group at a glance. Clustering methods do not require pre-defined categories as in classification methods. Thus, these methods are more adaptive for various types of queries. Nevertheless, clustering methods are more challenging than classification methods because they are conducted fully unsupervised. Moreover, most traditional clustering algorithms are infeasible for search result clustering, because of some practical issues. For example, the algorithm should take document snippets as input instead of the whole document, as downloading of the original document is time-consuming. The clustering algorithm should also be fast enough for online calculation. The generated clusters should have readable descriptions for quick browsing by users, etc.; however, traditional clustering techniques are inadequate because they do not generate clusters with highly readable names.
The IR (Information Retrieval) community has explored document clustering as an alternative method of organizing retrieval results, but clustering has yet to be deployed on most major search engines. Some of them apply traditional clustering algorithms that first cluster documents into topically coherent groups based on content similarity, and then generate descriptive summaries for clusters. However, these summaries are often unreadable, which make it difficult for Web users to identify relevant clusters.
Challenges within the snippet clustering problem include limited data (in the form of, for example, a URL (Universal Resource Locator), a title, and one or more snippets), speed (the clustering of several hundred snippets in a very short period of time, e.g., few seconds), and browsable summaries (the user needs to determine at a glance whether a cluster is of interest; therefore, the architecture needs to provide concise and accurate descriptions of the clusters).